//
//  131. 分割回文串.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/28.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution131 {
    var result: [[String]] = []
    var path: [String] = []
    func partition(_ s: String) -> [[String]] {
        let array = Array(s).map(String.init)
        backTrace(array, start: 0)
        return result
    }
    func backTrace(_ s: [String], start: Int) {
        if start >= s.count {
            result.append(path)
            return
        }
        for i in start..<s.count {
            let subArray = s[start...i]
            let subStr = subArray.joined()
            if isSymmetry(s, start: start, end: i) {
                path.append(subStr)
            } else {
                continue
            }
            backTrace(s, start: i + 1)
            path.removeLast()
        }
    }
    func isSymmetry(_ s: [String], start: Int, end: Int) -> Bool {
        var left = start
        var right = end
        while left < right {
            if s[left] != s[right] {
                return false
            }
            left += 1
            right -= 1
        }
        return true
    }
    static func test() {
        let str = "aab"
        let solution = Solution131()
        let result = solution.partition(str)
        print(result)
    }
}
